/*
整数划分是把一个正整数 N 拆分成一组数相加并且等于 N 的问题.
比如:
6
5 + 1 (序列)
	4 + 2, 4 + 1 + 1
	3 + 3, 3 + 2 + 1, 3 + 1 + 1 + 1
	2 + 2 + 2, 2 + 2 + 1 + 1, 2 + 1 + 1 + 1 + 1
	1 + 1 + 1 + 1 + 1 + 1

	假设F(N,M) 整数 N 的划分个数,其中 M 表示将 N 拆分后的序列中最大数

	考虑边界状态:
	M = 1 或者 N = 1 只有一个划分 既: F(1,1) = 1
	M = N : 等于把M - 1 的划分数加 1 既: F(N,N) = F(N,N-1) + 1
	M > N: 按理说,N 划分后的序列中最大数是不会超过 N 的,所以 F(N,M ) = F(N,N)
	M < N: 这个是最常见的, 他应该是序列中最大数为 M-1 的划分和 N-M 的划分之和, 比如F(6,4),上面例子第三行, 他应该等于对整数 3 的划分, 然后加上 2 的划分(6-4) 所以 F(N,M) = F(N, M-1) + F(N-M,M)

	DP的状态空间已经表示出来了.
	代码就很简单了:
*/

#include "junix.h"

uint64_t split(uint64_t n, uint64_t m)
{
	if(n < 1 || m < 1)
		return 0;
	if(n == 1 || m == 1)
		return 1;
	if(n < m)
		return split(n, n);
	if(n == m)
		return (split(n, m - 1) + 1);
	if(n > m)
		return (split(n, m - 1) + split((n - m), m));
}

int main()
{
	int n ;
	scanf("%d",&n);
	while ( n != 0 )
	{       
		printf("%d 的划分数: %I64ud\n", n, split(n, n));
		scanf("%d",&n);
	}
}
